#include<bits/stdc++.h>
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid ((l+r)>>1)
#define lc L,l,mid
#define rc R,mid+1,r
#define Root 1,1,n
#define OK Ll<=l&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
#define YY puts("Yes"),exit(0)
#define NN puts("No"),exit(0)
#define yy return puts("Yes"),void()
#define nn return puts("No"),void()
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=1e6+5,M=1e6+5,inf=(1LL<<30)-1,mod=6661;
const ll llf=1e18;
inline void add(int &a,int b){((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){return a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,ll b){if(!b)return 1;int c=qp(a,b>>1LL);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
inline bool che(int x,int p){return (x>>p)&1LL;}
int Cc[mod+5][mod+5],pr[mod+5][mod+5],n,m,a[N],fac[mod+5],iv[mod+5];
ll k;
inline void prep(){
	rep(i,0,mod-1)Cc[i][0]=pr[i][0]=1;
	rep(i,1,mod-1)rep(j,1,i)Cc[i][j]=Add(Cc[i-1][j],Cc[i-1][j-1]),pr[i][j]=Add(pr[i][j-1],Cc[i][j]);
	fac[0]=1;
	rep(i,1,mod-1)fac[i]=mul(fac[i-1],i);
	iv[mod-1]=INV(fac[mod-1]);
	per(i,mod-2,0)iv[i]=mul(iv[i+1],i+1);
}
inline int Get(int X,int l,int r){
	r=min(r,X);
	if(l>r)return 0;
	return Red(pr[X][r],pr[X][l-1]);
}
inline int inv(int x){
	return mul(iv[x],fac[x-1]);
}
ll K[N];
int s[N];
map<int,int>P;
inline int getbel(int x){//<=x last
	auto it=P.lower_bound(x);
	if(it==P.end())it--;
	if((*it).first>x)it--;
	return (*it).first;
}
inline void solve(int l,int r,ll k){
	int le=getbel(l),re=getbel(r);
	if(le==re){
		int Ll=le,Rr=P[le];
		P.erase(Ll);
		if(Ll<l)P[Ll]=l-1;
		if(Rr>r)P[r+1]=Rr,K[r+1]=K[Ll],s[r+1]=s[le]+r+1-le;
		P[l]=r,K[l]=k,s[l]=1;
		return;
	}
	int now=P[le]+1;
	while(now<re){
		int Rr=P[now];
		P.erase(now),now=Rr+1;
	}
	int Ll=le,Rr=P[re];
	P.erase(le),P.erase(re);
	if(Ll<l)P[Ll]=l-1;
	if(Rr>r)P[r+1]=Rr,K[r+1]=K[re],s[r+1]=s[re]+r+1-re;
	P[l]=r,K[l]=k,s[l]=1;
}
inline int calc(ll k,int t){//t:length
	int G=k%mod;
	if(t>G)return 0;
	return mul(fac[G],iv[G-t]);
}
inline int Calc(int l,int r,int Ll,int Rr){
	if(r<Ll||l>Rr)return 0;
	Rr=min(r,Rr),Ll=max(Ll,l);
	ll k=K[l];
	int sx=s[l]+Ll-l,ans=0;//C(k,sx) start
	if(sx>k)return 0;
	int t=sx/mod,G=mul(iv[t],calc(k/mod,t)),res=mod-sx%mod,now;
	if(Rr-Ll+1<=res)return mul(G,Get(k%mod,sx%mod,sx%mod+Rr-Ll));
	ans=mul(G,Get(k%mod,sx%mod,mod-1)),now=Ll+res;
	while(now<=Rr){
		t++;
		if(k/mod-t+1<=0)return ans;
		Mul(G,mul(inv(t),(k/mod-t+1)%mod));
		add(ans,mul(G,Get(k%mod,0,min(mod-1,Rr-now))));
		now+=mod;
	}
	return ans;
}
inline int query(int l,int r){
	int le=getbel(l),re=getbel(r);
	int now=le,ans=0;
	while(now<=re)add(ans,Calc(now,P[now],l,r)),now=P[now]+1;
	return ans;
}
inline void Main(){
	n=read(),m=read(),cin>>k;
	P[1]=n,K[1]=k,s[1]=1;
	while(m--){
		int ty=read(),l=read(),r=read();
		if(ty==1)cin>>k,solve(l,r,k);
		else printf("%d\n",query(l,r));
	}
}
signed main(){
	freopen("izumi.in","r",stdin);
	freopen("izumi.out","w",stdout);
	prep();
	int T=1;
	while(T--)Main();
	return 0;
}
